package de.h_da.fbi.cg.pointcloud.adt;

import java.util.ArrayList;

import de.h_da.fbi.cg.pointcloud.util.Quicksort;

/**
 * @author Nicolas Gramlich
 * @since 09:54:02 - 11.11.2010
 */
public class Graph {
	// ===========================================================
	// Constants
	// ===========================================================

	// ===========================================================
	// Fields
	// ===========================================================

	final VertexList mVertices = new VertexList();
	final EdgeList mEdges = new EdgeList();

	// ===========================================================
	// Constructors
	// ===========================================================

	// ===========================================================
	// Getter & Setter
	// ===========================================================

	public VertexList getVertices() {
		return this.mVertices;
	}

	public EdgeList getEdges() {
		return this.mEdges;
	}

	// ===========================================================
	// Methods for/from SuperClass/Interfaces
	// ===========================================================

	// ===========================================================
	// Methods
	// ===========================================================

	public void addEdge(final Edge pEdge) {
		this.mEdges.add(pEdge);
	}

	public void addEdges(final ArrayList<Edge> pEdges) {
		final int edgeCount = pEdges.size();

		final ArrayList<Edge> edges = this.mEdges;
		for(int i = 0; i < edgeCount; i++) {
			edges.add(pEdges.get(i));
		}
	}

	public void addVertex(final Vertex pVertex) {
		this.mVertices.add(pVertex);
		pVertex.setGraph(this);
	}

	public void addVertices(final ArrayList<Vertex> pVertices) {
		final int vertexCount = pVertices.size();

		final ArrayList<Vertex> vertices = this.mVertices;
		for(int i = 0; i < vertexCount; i++) {
			final Vertex vertex = pVertices.get(i);
			vertex.setGraph(this);
			vertices.add(vertex);
		}
	}

	public Edge getShortestOutgoingEdge() {
		final ArrayList<Edge> edges = this.mEdges;
		Quicksort.sort(edges);

		final int edgeCount = edges.size();
		for(int i = 0; i < edgeCount; i++) {
			final Edge edge = edges.get(i);
			if(edge.isInterComponentEdge()) {
				return edge;
			}
		}

		return null;

		//		final UniqueArrayList<Edge> edges = this.mEdges;
		//		Edge shortest = null;
		//		float shortestLength = Float.MAX_VALUE;
		//
		//		final int edgeCount = edges.size();
		//		for(int i = 0; i < edgeCount; i++) {
		//			final Edge edge = edges.get(i);
		//			if(edge.isOutgoing()) {
		//				if(edge.mLength < shortestLength) {
		//					shortestLength = edge.mLength;
		//					shortest = edge;
		//				}
		//			}
		//		}
		//
		//		return shortest;
	}

	public void union(final Graph pGraph) {
		this.addVertices(pGraph.mVertices);
		this.removeNonEMSTInternalEdges();
		this.addOutgoingEdges(pGraph);
	}

	private void addOutgoingEdges(final Graph pGraph) {
		final ArrayList<Edge> pEdges = pGraph.mEdges;
		final int edgeCount = pEdges.size();

		final ArrayList<Edge> edges = this.mEdges;
		for(int i = 0; i < edgeCount; i++) {
			final Edge edge = pEdges.get(i);
			if(edge.isInterComponentEdge() || edge.mEuclideanMinumumSpanningTreeEdge) {
				edges.add(edge);
			}
		}
	}
	
	private void removeNonEMSTInternalEdges() {
		/* TODO This is currently the main performance-killer with ~60% CPU used. */
		final ArrayList<Edge> edges = this.mEdges;
		for(int i = edges.size() - 1; i >= 0; i--) {
			final Edge edge = edges.get(i);
			if(edge.isIntraComponentEdge() && !edge.mEuclideanMinumumSpanningTreeEdge) {
				edges.remove(i);
			}
		}
	}

	@Override
	public String toString() {
		return "Graph [\n\tEdges:\n\t\t" + this.mEdges + "\n\tVertices:\n\t\t" + this.mVertices + "\n]";
	}

	// ===========================================================
	// Inner and Anonymous Classes
	// ===========================================================
}
